\chapter{Codes correcteurs}

	\section{Définition d'un code correcteur}

		Dans cette section nous allons formaliser l'idée de codes correcteurs telle qu'ébauchée dans l'introduction.
		L'idée est bien sur d'enrichir via le codage un message de taille k avec de la redondance pour obtenir un nouveau message de taille n.
		Il faut donc  $ k < n  $ .

		\begin{defi} \label{code} \cite{04cc}
			Un code en bloc  $ \mathbf{C} $  est l'image d'une application injective  $ \mathbf{f} $  de  $ \mathbb{F}_{q}^{k} $  dans  $ \mathbb{F}_{q}^{n} $ .
			Ce code est dit linéaire si f est une application linéaire.
			 $$ \mathbf{f} : \mathbb{F}_{q}^{k} \rightarrow \mathbb{F}_{q}^{n}  $$ 
		\end{defi}

		Nous avons aussi soulevé l'idée que pour mieux reconnaître le message d'origine, il fallait séparer les mots de code entre eux.
		Pour cela nous définissons une notion de distance.

		\begin{defi} \label{distance}
			La distance de Hamming est l'application  $ \mathbf{d} $  de  $ \mathbb{F}_{q}^{n} \times \mathbb{F}_{q}^{n} $  dans  $ \mathbb{N} $  définie par :
			 $$ \mathbf{d} : (a,b) \in \mathbb{F}_{q}^{n} \times \mathbb{F}_{q}^{n} \mapsto card(i \in \mathbb{N} / a_{i} \neq b_{i}) $$ 
		\end{defi}

		Maintenant que nous avons l'outil pour constater la séparation des mots de code, nous introduisons la notion de distance minimale entre deux mots. Cette distance donne un ensemble de boules chacune centrée sur un mot de code qui ne s'intersectent pas deux à deux.

		\begin{defi} \label{correction}
			On note t la capacité de correction d'un code correcteur, par définition :
			 $$ t = \max_{r \in \mathbb{N}}  \bigcap_{x \in \mathbf{C}} B(x,r) = \emptyset $$ 
			De manière évidente on a l'inégalité :  $ 2t+1 \leq d $ 
		\end{defi}

		Nous définissons enfin une application permettant de retrouver le message d'origine.

		\begin{defi} \label{decodage}
			On appelle un décodage l'application 
			 $ \mathbf{D} : \mathbb{F}_{q}^{n} \rightarrow \mathbb{F}_{q}^{k}  $ 
			telle que  $ \mathbf{D} \circ \mathbf{f} = Id_{F_{q}^{k}}  $ .
			 $ \mathbf{D} $  est de vraisemblance maximale si : 
			 $$ \forall x \in \mathbf{C}, \mathbf{D}(B(x,t)) = {x}    $$ 
		\end{defi}

	\section{Utilisation des codes correcteurs}

		Nos codes correcteurs sont pour l'instant des ensembles de mots d'un espace de dimension plus grande que l'espace des messages.
		L'intérêt d'utiliser des applications linéaires est de pouvoir définir l'ensemble  $ \mathbf{C} $  avec un minimum d'informations.
		La seule donnée de l'image des vecteurs de base définit entièrement  $ \mathbf{f} $  et  $ \mathbf{C} $ , donc le codage.

		\begin{defi} \label{generatrice}
			On appelle G  matrice génératrice du code  $ \mathbf{C} $  la matrice de  $ \mathbf{f} $  dans la base canonique.
			 $$ G \in M_{n,k}(\mathbb{F}_{q}), G = Mat(\mathbf{f})  $$ 
		\end{defi}

		\begin{defi} \label{parite}
			On appelle H matrice de parité du code  $ \mathbf{C} $  une matrice telle que :
			 $$ H \in M_{n-k,n}(\mathbb{F}_{q}), Ker(H) = \mathbf{C}  $$ 
			L'application  $ x \in \mathbb{F}^{n} \rightarrow Hx  $  s'appelle le syndrome de  $ x $ .
		\end{defi}

		Nous avons défini le codage de manière linéaire, il est impossible de faire de même pour le décodage. 
		Nous allons donc utiliser la matrice de parité pour introduire la notion de syndrome qui va permettre le décodage.

		\begin{prop} \label{syndrome}
			A la réception d'un message de  $ \mathbb{F}^{n} $ , en considérant que le nombre d'erreurs est inférieur a t, donc que le vecteur d'erreur  $ \epsilon $  a un poids inférieur ou égal a t, on a :
			 $ \forall m \in \mathbb{F}^{n}, \exists ! (x,\epsilon) \in \mathbf{C} \times \mathbb{F}^{n} $  tels que :
			 $$  \left\{
				\begin{array}{r c l}
				m &=& x + \epsilon \\
				\mathbf{d}(\epsilon) &\leq& t \\
				Hm &=& H \epsilon
				\end{array}
			\right.  $$ 
		\end{prop}

		Le principe est de déterminer  $ \epsilon $ . On retrouve ainsi le mot de code d'origine  $ x = m - \epsilon $ 

		\begin{prop} \label{erreur}
			 $ \forall m \in \mathbb{F}^{n} $ , son syndrome est caractéristique de l'erreur, dans l'hypothèse d'un maximum de t erreurs. 
			Supposons deux vecteurs d'erreurs avec le même syndrome :
			 $$ 
			H \epsilon = H \eta \Rightarrow H(\epsilon - \eta) = 0 \Rightarrow \epsilon - \eta \in \mathbf{C}
			 $$ 
			D'après l'inégalité triangulaire,  $ d(\epsilon - \eta) \leq 2t < d  $  donc  $ \epsilon - \eta = 0 $  
		\end{prop}

		Néanmoins cette méthode est relativement limitée en l'état.
		Pour un code linéaire quelconque, la reconnaissance du syndrome est un problème jugé difficile.
		L'enjeu de la théorie des codes va être de construire des structures de codes rendant le problème plus simple.
		Dans la suite de ce TIPE nous nous intéresserons aux codes de Goppa dont l'usage principal sera le cryptosystème de Mc Eliece étudié dans la partie 3.